class Solution {
    public:
        int countSubstrings(string s) {
            //dp i j 表示以i-j位置的子串是否是回文串
            int n = s.size();
            vector<vector<bool>> dp(n,vector<bool>(n));
            dp[n-1][n-1] = true;
            int ret = 1;
            for(int i = n-2 ; i >= 0 ; i--){
                for(int j = i ; j < n ; j++){
                    if(s[i] == s[j]){
                        if(i+1 == j){
                            dp[i][j] = true;
                        }else if(i == j){
                            dp[i][j] = true;
                        }else if(dp[i+1][j-1] ==true ){
                            dp[i][j] = true;
                        }else{
                            dp[i][j] == false;
                        }
                    }else{
                        dp[i][j] = false;
                    }
                    if(dp[i][j] == true) ret++;
                }
            }
            return ret;
        }
    };